/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode *dummy=new ListNode(0);
         dummy->next=head;
        ListNode *pre=dummy;
        ListNode *end=dummy;//这里的dummydummy node 很巧妙，当节点数不足k个时，和至少能满足一次kk个翻转，都可以保证正确返回头节点
       // dummy->next=head;
        
        
        
        while(end->next!=nullptr)
        {
        for(int i=0;i<k &&end!=nullptr;i++)   //// 通过for找到反转node的范围，何时结束?当end->next==nullptr时，结束
        {                                                //为此在for外层加while(end->next==nullptr)
            end=end->next;                      //而且要注意， 这里的k次遍历后end刚好是第k个点，之所以有这样的结果是因为end的初始位置是链表头的前一个位置
        }
        if(end==nullptr)
        {
            break;
        }
        //先断链，再reverse  断链前存一下end->next
        ListNode *next=end->next;
            /*
        ListNode *start=pre->next;  //这里要用新节点  pre->next  ？考虑下 是否不一定需要
        end->next=nullptr; ///注意反转之后要修回断掉的链
        pre->next=reverse(start);   //返回的是翻转后的链表的头
        start->next=next;
        pre=start;
        end=start;
        */    //翻转 1 2 3  to  3 2 1
        ListNode *start=pre->next;//保存下一次要翻转k个的pre节点   即是翻转前的head 翻转后的尾节点
        end->next=nullptr;//注意这里要断链
        pre->next=reverse(pre->next);  //连接翻转后的左端  即三接到已翻转的部分. 翻转的链表结果应该被之前已经翻转的节点的末节点指向
        start->next=next;  //连接翻转后的右端 即 1的next接到未翻转的链表
        pre=start;    //将pre和end置到下一次要翻转k个node的前一位置 ,注意这巧妙的start
        end=start  //
            
        }
        return dummy->next;
        
    }
            
            
      ListNode* reverse(ListNode* head)
        {
          ListNode *pre=nullptr;
          ListNode *curr=nullptr;
          while(head!=nullptr)
          
          {
              curr=head->next;
              head->next=pre;
              pre=head;
              head=curr;      
          }
          return pre;
            
        }

};